/**
 * 加一
 *
 * 给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。
 * 这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。
 * 将大整数加 1，并返回结果的数字数组。
 *
 * 示例 1：
 * 输入：digits = [1,2,3]
 * 输出：[1,2,4]
 * 解释：输入数组表示数字 123。
 * 加 1 后得到 123 + 1 = 124。
 * 因此，结果应该是 [1,2,4]。
 * 示例 2：
 * 输入：digits = [4,3,2,1]
 * 输出：[4,3,2,2]
 * 解释：输入数组表示数字 4321。
 * 加 1 后得到 4321 + 1 = 4322。
 * 因此，结果应该是 [4,3,2,2]。
 * 示例 3：
 * 输入：digits = [9]
 * 输出：[1,0]
 * 解释：输入数组表示数字 9。
 * 加 1 得到了 9 + 1 = 10。
 * 因此，结果应该是 [1,0]。
 *
 * 提示：
 * 1 <= digits.length <= 100
 * 0 <= digits[i] <= 9
 * digits 不包含任何前导 0。
 */

/**
 * 这题难点不就是让咱进位嘛, 咱从后面开始算, 一直向前加, 遇到要进位的咱就进位
 * 但是我们留个心眼子, 我们在最后一位的时候不改变 nums[0] 的值, 因为这样我们
 * 就好将数组扩容, 咱后面只需要看一下进位之后的最后一位是否是 0 考虑是否要扩容
 * 就可以了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {
    public int[] plusOne(int[] nums) {

        // 数组原长
        int n = nums.length;

        // 进位标志
        int tmp = 1;

        // 从后向前遍历
        for (int i = n - 1; i >= 0; i--) {

            // 要是中途进位为 0, 那么直接退出就可以了
            if (tmp == 0) {
                break;
            }

            // 进位
            nums[i] += tmp;

            // 更新进位符
            tmp = nums[i] / 10;

            // 第一个位置不要改
            if (i != 0) {
                nums[i] %= 10;
            }
        }

        if (nums[0] == 10) {

            // 看下第一个位置是否为 10, 要是为 10 说明要扩容
            int[] arr = new int[n + 1];
            arr[0] = 1;
            arr[1] = 0;
            for (int i = 2; i <= n; i++) {
                arr[i] = nums[i - 1];
            }
            return arr;
        } else {

            // 不为 0 , 不需要扩容
            return nums;
        }
    }
}